package MyBinaryTree;

import java.util.*;

public class MyBinaryTree implements Operation{

    public int size;

    public int leafSize;

    public TreeNode createTree() {
        TreeNode A = new TreeNode(1);
        TreeNode B = new TreeNode(2);
        TreeNode C = new TreeNode(3);
        TreeNode D = new TreeNode(4);
        TreeNode E = new TreeNode(5);
        TreeNode F = new TreeNode(6);
        TreeNode G = new TreeNode(7);

        A.leftNode = B;
        A.rightNode = C;
//        B.leftNode = D;
//        B.rightNode = E;
//        C.leftNode = F;
//        C.rightNode = G;

        return A;
    }

    public static int i;
    public TreeNode createTree(String str) {
        TreeNode node = null;
        if (str.charAt(i) != '#') {
            node = new TreeNode(str.charAt(i));
            i++;
            node.leftNode = createTree(str);
            node.rightNode = createTree(str);
        } else {
            i++;
        }

        return node;
    }

    // 前序遍历
    public void preOrder(TreeNode rootNode) {
        TreeNode curNode = rootNode;

        if (curNode == null) {
            return;
        }

        System.out.print(curNode.val + " ");

        this.preOrder(curNode.leftNode);
        this.preOrder(curNode.rightNode);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            list.add(cur.val);
            if (cur.rightNode!= null) {
                stack.push(cur.rightNode);
            }
            if (cur.leftNode != null) {
                stack.push(cur.leftNode);
            }
        }
        return list;
    }

    // 中序遍历
    public void inOrder(TreeNode rootNode) {
        TreeNode curNode = rootNode;

        if (curNode == null) {
            return;
        }

        this.inOrder(curNode.leftNode);
        System.out.print(curNode.val + " ");
        this.inOrder(curNode.rightNode);
    }

     public static void inOrder(String str) {
         Stack<Character> stack = new Stack<>();
         for (int i = 0; i < str.length(); i++) {
             char ch = str.charAt(i);
             if (ch != '#') {
                 stack.push(ch);
             } else {
                 if (!stack.isEmpty()) {
                     System.out.print(stack.pop() + " ");
                 } else {
                     break;
                 }
             }
         }
     }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.leftNode;
            }

            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.rightNode;
        }
        return list;
    }

    // 后序遍历
    public void postOrder(TreeNode rootNode) {
        TreeNode curNode = rootNode;

        if (curNode == null) {
            return;
        }

        this.postOrder(curNode.leftNode);
        this.postOrder(curNode.rightNode);
        System.out.print(curNode.val + " ");
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        Stack<TreeNode> stack = new Stack<>();
        Queue<TreeNode> queue = new LinkedList<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            queue.offer(cur);
            if (cur.leftNode != null) {
                stack.push(cur.leftNode);
            }
            if (cur.rightNode != null) {
                stack.push(cur.rightNode);
            }
        }

        for (TreeNode cur : queue) {
            stack.push(cur);
        }

        // for (TreeNode cur : stack) {
        //     list.add(cur.val);
        // }

        while (!stack.isEmpty()) {
            list.add(stack.pop().val);
        }

        return list;
    }

    //遍历思路
    @Override
    public int size(TreeNode root) {
        //int size = 0;

        TreeNode curNode = root;

        if (curNode == null) {
            return size;
        } else {
            size++;
        }

        size(curNode.leftNode);
        size(curNode.rightNode);

        return size;

    }

    //子问题思路
    public int size2(TreeNode root) {
        TreeNode curNode = root;

        if (curNode == null) {
            return 0;
        }

        return size2(curNode.leftNode) + size2(curNode.rightNode) + 1;
    }

    //子问题思路
    @Override
    public int getLeafNodeCount(TreeNode root) {
        TreeNode curNode = root;

        if (curNode.leftNode == null && curNode.rightNode == null) {
            return 1;
        } else if (curNode == null) {
            return 0;
        }

        return getLeafNodeCount(curNode.leftNode) + getLeafNodeCount(curNode.rightNode);

    }

    //遍历思路
    public void getLeafNodeCount2(TreeNode root) {
        TreeNode curNode = root;

        if (curNode == null) {
            return;
        } else if (curNode.leftNode == null && curNode.rightNode == null) {
            this.leafSize++;
        }

        getLeafNodeCount2(curNode.leftNode);
        getLeafNodeCount2(curNode.rightNode);
    }

    //子问题思路
    @Override
    public int getKLevelNodeCount(TreeNode root, int k) {
        TreeNode curNode = root;

        if (curNode == null) {
            return 0;
        }

        if (k == 1 && curNode != null) {
            return 1;
        }

        return getKLevelNodeCount(curNode.leftNode, k - 1) + getKLevelNodeCount(curNode.rightNode, k - 1);
    }

    public int KLevelNodeCount;
    //遍历思路
    public int getKLevelNodeCount2(TreeNode root, int k) {
        TreeNode curNode = root;

        //int count = 0;

        if (curNode == null) {
            return 0;
        }

        if (k == 1) {
            KLevelNodeCount++;
        }

        getKLevelNodeCount2(curNode.leftNode, k - 1);
        getKLevelNodeCount2(curNode.rightNode, k - 1);

        return KLevelNodeCount;
    }

    //遍历思路
    @Override
    public int getHeight(TreeNode root) {
        TreeNode curNode = root;

        if (curNode == null) {
            return 0;
        }

        int leftHeight = getHeight(curNode.leftNode);
        int rightHeight = getHeight(curNode.rightNode);

        return Math.max(leftHeight, rightHeight) + 1;
    }

    public int height;
    //子问题思路
    public int getHeight2(TreeNode root) {
        TreeNode curNode = root;

        if (curNode == null) {
            return 0;
        } else {
            height++;
        }

        return Math.max(getHeight2(curNode.leftNode), getHeight2(curNode.rightNode)) + 1;
    }


    @Override
    public TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }

        if (root.val == val) {
            return root;
        }

        TreeNode left = find(root.leftNode, val);
        if (left != null) {
            return left;
        }

        TreeNode right = find(root.rightNode, val);
        if (right != null) {
            return right;
        }

        return null;
    }

    @Override
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            System.out.print(curNode.val + " ");
            if (curNode.leftNode != null) {
                queue.offer(curNode.leftNode);
            }
            if (curNode.rightNode != null) {
                queue.offer(curNode.rightNode);
            }
        }

        System.out.println();
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();

        List<List<Integer>> list = new ArrayList<>();
//        List<Integer> list1 = new ArrayList<>();

        if (root == null) {
            return null;
        }

        q1.offer(root);

        while (!q1.isEmpty() || !q2.isEmpty()) {
            List<Integer> list1 = new ArrayList<>();
            if (!q1.isEmpty()) {
                while (!q1.isEmpty()) {
                    TreeNode cur = q1.poll();
                    list1.add(cur.val);
                    if (cur.leftNode != null) {
                        q2.offer(cur.leftNode);
                    }
                    if (cur.rightNode != null) {
                        q2.offer(cur.rightNode);
                    }
                }
            } else {
                while (!q2.isEmpty()) {
                    TreeNode cur = q2.poll();
                    list1.add(cur.val);
                    if (cur.leftNode != null) {
                        q1.offer(cur.leftNode);
                    }
                    if (cur.rightNode != null) {
                        q1.offer(cur.rightNode);
                    }
                }
            }
            list.add(list1);
//            list1.clear();
        }

        return list;
    }

    @Override
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();

        if (root == null) {
            return false;
        }

        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            if (curNode == null) {
                break;
            }
            queue.offer(curNode.leftNode);
            queue.offer(curNode.rightNode);
        }

        for (TreeNode node : queue) {
            if (node != null) {
                return false;
            }
        }

        return true;
    }

    public boolean isSameTree1(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }

        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();

        queue1.offer(p);
        queue2.offer(q);

        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode curp = queue1.poll();
            TreeNode curq = queue2.poll();
            if (curp == null && curq != null || curp != null && curq == null) {
                return false;
            } else if (curp == null && curq == null) {
                continue;
            } else if (curp.val != curq.val) {
                return false;
            }

            // if (curp.left != null) {
            //     queue1.offer(curp.left);
            // }
            // if (curp.right != null) {
            //     queue1.offer(curp.right);
            // }
            // if (curq.left != null) {
            //     queue2.offer(curq.left);
            // }
            // if (curq.right != null) {
            //     queue2.offer(curq.right);
            // }

            queue1.offer(curp.leftNode);
            queue1.offer(curp.rightNode);
            queue2.offer(curq.leftNode);
            queue2.offer(curq.rightNode);
        }

        if (!queue1.isEmpty() || !queue2.isEmpty()) {
            return false;
        } else {
            return true;
        }
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null || p != null && q == null) {
            return false;
        }

        if (p == null && q == null) {
            return true;
        }

        if (p.val != q.val) {
            return false;
        }

        return isSameTree(p.leftNode, q.leftNode) && isSameTree(p.rightNode, q.rightNode);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }

        if(isSameTree(root, subRoot)) {
            return true;
        }

        if (isSubtree(root.leftNode, subRoot)) {
            return true;
        }
        if (isSubtree(root.rightNode, subRoot)) {
            return true;
        }

        return false;
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode cur = root;

        TreeNode temp = cur.leftNode;
        cur.leftNode = cur.rightNode;
        cur.rightNode = temp;

        invertTree(cur.leftNode);
        invertTree(cur.rightNode);

        return root;
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        int left = getHeight(root.leftNode);
        int right = getHeight(root.rightNode);

        if (Math.abs(left - right) > 1) {
            return false;
        }

        return isBalanced(root.leftNode) && isBalanced(root.rightNode);
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return isSymmetric2(root.leftNode, root.rightNode);
    }

    public boolean isSymmetric2(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null && right != null || left != null && right == null) {
            return false;
        } else if (left.val != right.val) {
            return false;
        }

        return isSymmetric2(left.leftNode, right.rightNode) && isSymmetric2(left.rightNode, right.leftNode);

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.leftNode, p, q);
        TreeNode right = lowestCommonAncestor(root.rightNode, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }

    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        tree2str2(root, str);
        return str.toString();
    }

    public void tree2str2(TreeNode root, StringBuilder str) {
        if (root == null) {
            return;
        }

        str.append(root.val);

        if (root.leftNode != null) {
            str.append("(");
            tree2str2(root.leftNode, str);
            str.append(")");
        } else {
            if (root.rightNode == null) {
                return;
            } else {
                str.append("()");
            }
        }

        if (root.rightNode != null) {
            str.append("(");
            tree2str2(root.rightNode, str);
            str.append(")");
        } else {
            return;
        }
    }
}
